package com.dmall.chapter07.section03;

import java.util.*;
import java.util.stream.Collectors;

public class LeetCode752 {

    public int openLock(String[] deadends, String target) {
        String startLock = "0000";
        Set<String> deadSet = Arrays.stream(deadends).collect(Collectors.toSet());
        if (deadSet.contains(target) || deadSet.contains(startLock)) {
            return -1;
        }
        if (startLock.equals(target)) {
            return 0;
        }
        Map<String, Integer> visited = new HashMap<>();
        Queue<String> queue = new LinkedList<>();
        queue.add(startLock);
        visited.put(startLock, 0);
        while (!queue.isEmpty()) {
            String curs = queue.remove();
            char[] chars = curs.toCharArray();
            List<String> list = new ArrayList<>();
            for (int i = 0; i < 4; i++) {
                char o = chars[i];
                chars[i] = Character.forDigit((chars[i] - '0' + 1) % 10, 10);
                list.add(new String(chars));
                chars[i] = o;

                chars[i] = Character.forDigit((chars[i] - '0' + 9) % 10, 10);
                list.add(new String(chars));
                chars[i] = o;
            }

            for (String s : list) {
                if (!deadSet.contains(s) && !visited.containsKey(s)) {
                    queue.add(s);
                    visited.put(s, visited.get(curs) + 1);
                    if (s.equals(target)) {
                        return visited.get(s);
                    }
                }
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        String[] deadends = {"0201", "0101", "0102", "1212", "2002"};
        String target = "0202";
        LeetCode752 leetCode752 = new LeetCode752();
        int result = leetCode752.openLock(deadends, target);
        System.out.println(result);
    }
}
